package math;

/**
 * @Author Fizz Pu
 * @Date 2021/5/15 下午8:17
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class YUESEFUHUAN62 {
    public static void main(String[] args) {
        System.out.println(new YUESEFUHUAN62().lastRemaining(5, 3));
    }

    /*public int lastRemaining(int n, int m) {

        *//*int[] circle = new int[n];// circle[i] = 1 表示i被删除, circle[i] = 0, 表示i未被删除
        int restEleCount = n; // 未被删除的元素个数
        int start = -1; // 开始位置
        m = m % n;

        while (restEleCount > 1){
            // 进行m次有效的移动, 得到要删除的下标start
            int move = m;
            while (move > 0){
                start = (start + 1) % n;
                if(circle[start] == 0){
                    move--;
                 }
            }

            // 删除start
            circle[start] = 1;
            restEleCount--;

            // start更新为下一个位置的前一个位置
            int tmp;
            while (circle[tmp = ((start + 1) % n)] != 0 ){
                start = tmp;
            }
        }

        // 找到未删除的元素
        for(int i = 0; i < n; i++){
            if(circle[i] == 0){
                return i;
            }
        }

        throw new RuntimeException();
    }*//*
    */
    public int lastRemaining(int n, int m) {
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = i;
        }
        for (int i = 0; n > 1; --n) {
            i += m - 1;
            i %= n;
            System.arraycopy(data, i + 1, data, i, n - i - 1);
        }
        return data[0];
        }
}
